package offer_test_40;

//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。是则返回true，否则返回false。
public class four_SequenceOfBST {
	public static void main(String[] args) {
//		int[] array = { 5, 7, 6, 9, 11, 10, 8 };
//		 int[] array={7,4,6,5};
//		 int[] array={6,7,8,5};
		int [] array={};
		System.out.println(verifySequence(array));
	}

	public static boolean verifySequence(int[] array) {
	
		if(array.length==0||array.length==1){
			return true;
		}
		int root = array[array.length - 1];
		int left = array.length - 1;
		for (int i = 0; i < array.length; i++) {
			if (array[i] > root) {
				left = i;
				break;
			}
		}
		int[] leftarray = new int[left];
		int[] rightarray = new int[array.length - left-1];
		for (int i = 0; i < leftarray.length; i++) {
			leftarray[i] = array[i];
		}
		for (int i = 0; i < rightarray.length; i++) {
			rightarray[i]=array[left+i];
		}
		for(int i=0;i<rightarray.length;i++){
			if(rightarray[i]<root){
				return false;
			}
		}
		return verifySequence(leftarray)&&verifySequence(rightarray);
	}
}
